﻿//3298. 统计重新排列后包含另一个字符串的子字符串数目 II
//给你两个字符串 word1 和 word2 。
//如果一个字符串 x 重新排列后，word2 是重排字符串的前缀，那么我们称字符串 x 是 合法的 。
//请你返回 word1 中 合法子字符串的数目。
//注意 ，这个问题中的内存限制比其他题目要 小 ，所以你 必须 实现一个线性复杂度的解法。


class Solution {
public:
    int cur[26], tar[26];
    bool check()
    {
        for (int i = 0; i < 26; i++)
        {
            if (cur[i] < tar[i])
                return 0;
        }
        return 1;
    }
    long long validSubstringCount(string word1, string word2)
    {
        if (word1.length() < word2.length())
        {
            return 0;
        }
        long long ans = 0;
        for (auto& e : word2)
        {
            tar[e - 'a']++;
        }
        int left = 0, right = -1;
        int n = word1.size();
        for (right = 0; right < n; right++)
        {
            cur[word1[right] - 'a']++;
            while (check())
            {
                cur[word1[left++] - 'a']--;
            }
            ans += left;
        }
        return ans;
    }
};
